import java.util.*;

public class Leetcode40 {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates.length==0){
            return new ArrayList<>();
        }

        Arrays.sort(candidates);

        Deque<Integer> deque = new ArrayDeque<>();

        dfs(candidates,0,candidates.length,target,deque);
        return result;
    }

    public void dfs(int[] candidates,int index,int len,int target,Deque<Integer> deque){
            if (target==0){
                result.add(new ArrayList<>(deque));
                return;
                }
        for (int i = index; i < len; i++) {
            // 大剪枝
            if (target-candidates[index]<0){
                break;
            }
            // 小剪枝
            if (i>index&&candidates[i]==candidates[i-1]){
                continue;
            }
            deque.addLast(candidates[i]);
            dfs(candidates,i+1,len,target-candidates[i],deque);
            deque.removeLast();
        }

    }

}
